package problem225;
//255.用队列实现栈
//https://leetcode.cn/problems/implement-stack-using-queues/

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!q1.isEmpty()) {
            q1.add(x);
        }else {
            q2.add(x);
        }
    }

    public int pop() {
        if(!q1.isEmpty()) {
            while(q1.size() > 1) {
                q2.add(q1.poll());
            }
            return q1.poll();
        }else {
            while(q2.size() > 1) {
                q1.add(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        if(!q1.isEmpty()) {
            while(q1.size() > 1) {
                q2.add(q1.poll());
            }
            int ret = q1.peek();
            q2.add(q1.poll());
            return ret;
        }else {
            while(q2.size() > 1) {
                q1.add(q2.poll());
            }
            int ret = q2.peek();
            q1.add(q2.poll());
            return ret;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

//1.push: 哪个队列不为空就入哪个
//2.pop: 哪个队列不为空就出哪个, 出size-1个元素